package com.ww.springboot.boot.algorithm.leetcode1;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * todo
 *
 * @author wanwei
 * @since 2022-03-18 14:17
 */
public class AV91解码方法 {

    public static void main(String[] args) {
        String ss = "1111111111111111111111111111111111111111111111111111111111111111111111111111301";
        System.out.println(numDecodings2(ss));
    }

    /**
     * 回溯  如果字符太长 递归太深  考虑使用动态规划-递推
     *
     * @param ss
     * @return
     */
    public static int numDecodings(String ss) {
        char[] chars = ss.toCharArray();
        List<String> list = new ArrayList<>();
        numDecodings(chars, 0, list);
        return list.size();
    }


    /**
     * 根据字符分场景
     * f(n)= f(n-1)+f(n-2)
     * f(n)= f(n-2)
     * f(n)= 0
     *
     * @param ss
     * @return
     */
    public static int numDecodings2(String ss) {
        Map<String, Integer> map = new HashMap<>();
        int total = numDecodings2(ss, map);
        return total;
    }


    /**
     * 用递归 缓存
     *
     * @param ss
     * @param map
     * @return
     */
    public static int numDecodings2(String ss, Map<String, Integer> map) {
        Integer total = map.get(ss);
        if (total != null) {
            return total;
        }
        total = 0;

        if (ss.length() > 2) {
            if (ss.charAt(0) == '0' || (ss.charAt(0) > '2' && ss.charAt(1) == '0')) {
                total = 0;
            } else if (ss.charAt(0) > '2' || (ss.charAt(0) == '2' && ss.charAt(1) > '6')) {
                total = numDecodings2(ss.substring(1), map);
            } else if (ss.charAt(1) == '0') {
                total = numDecodings2(ss.substring(2), map);
            } else {
                total = numDecodings2(ss.substring(1), map) + numDecodings2(ss.substring(2), map);
            }
        } else if (ss.length() == 2) {
            if (ss.charAt(0) == '0' || (ss.charAt(0) > '2' && ss.charAt(1) == '0')) {
                total = 0;
            } else if (ss.charAt(0) > '2' || (ss.charAt(0) == '2' && ss.charAt(1) > '6')) {
                total = 1;
            } else if (ss.charAt(1) == '0') {
                total = 1;
            } else {
                total = 2;
            }
        } else if (ss.length() == 1) {
            if (ss.charAt(0) == '0') {
                total = 0;
            } else {
                total = 1;
            }
        }
        map.put(ss, total);
        return total;
    }

    /**
     * 回溯
     */
    public static void numDecodings(char[] chars, int index, List<String> list) {
        if (index < chars.length - 1) {
            //说明剩余的字符数大于等于2
            if (chars[index] > '2' || (chars[index] == '2' && chars[index + 1] > '6')) {
                //如果超过26 则只能一个字符为一组
                numDecodings(chars, index + 1, list);

            } else if (chars[index] == '0') {
                return;
                //如果第一个字符为0 则直接返回
            } else if (chars[index + 1] == '0') {
                //如果第二个字符为0 则只能选择两个字符组合在一起
                numDecodings(chars, index + 2, list);
            } else {
                //否则有两种选择
                numDecodings(chars, index + 1, list);
                numDecodings(chars, index + 2, list);
            }
        } else if (index == chars.length - 1) {
            //说明只剩一个字符 只要不是0 就可以
            if (chars[index] == '0') {
                return;
            } else {
                list.add("1");
            }
        } else {
            //说明已经遍历完成了
            list.add("1");
        }
    }
}
